1366C - Palindromic Paths - CodeForces Solution


greedy math *1500

Please click on ads to support us..

Python Code:

for t in range(int(input())):
    n,m=map(int,input().split());mat,dist,sum = [],dict(),0
    for i in range(n+m-2):dist[i]=[0,0]
    for ii in range(n):
        mat.append(list(map(int,input().split())))
        for iii in range(m):
            if 2*(ii+iii) != n+m-2:dist[min(ii+iii,n+m-2-ii-iii)][mat[ii][iii]] +=1
    for val in dist:sum+=min(dist[val])
    print(sum)
num_inp=lambda: int(input())
arr_inp=lambda: list(map(int,input().split()))
sp_inp=lambda: map(int,input().split())
str_inp=lambda:input()

C++ Code:

#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<cstring>
#define AboNasser cin.tie(nullptr); ios::sync_with_stdio(false);
using namespace std;
#define ll long long
typedef pair<int, int> pr;
typedef vector<ll> vll;
ll mod = 1e9 + 7;
ll n;
ll dp[1000001][2];



void solve()
{
    int n, m;
    cin >> n >> m;
    int arr[31][31];
    if (m >= n)
    {
        for (int i = 0;i < n;i++)
            for (int j = 0;j < m;j++)
                cin >> arr[i][j];
    }
    else
    {
        for (int j = 0;j < n;j++)
            for (int i = 0;i < m;i++)
                cin >> arr[i][j];
        swap(n, m);
    }
   
    ll ans = 0;
   
    for (int j = 0;j < (m + n - 1) / 2;j++)
    {
        int x = j, y = 0;
        ll o = 0, z = 0;
        while (x > -1 && y < n)
        {
            if (arr[y][x] == 0)
                z++;
            else
                o++;
            y++, x--;
        }
        x = m - j - 1;
        y = n - 1;
        while (x < m && y > -1)
        {
            if (arr[y][x] == 0)
                z++;
            else
                o++;
            y--, x++;
        }
        ans += min(z, o);
    }
    cout << ans << endl;
}




int main()

{
    AboNasser
        //	freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);

        ll t;
     cin >> t;
     while (t--)
    solve();
    return 0;

}


Comments

Submit
0 Comments
More Questions

2. Add Two Numbers
515. Find Largest Value in Each Tree Row
345. Reverse Vowels of a String
628. Maximum Product of Three Numbers
1526A - Mean Inequality
1526B - I Hate 1111
1881. Maximum Value after Insertion
237. Delete Node in a Linked List
27. Remove Element
39. Combination Sum
378. Kth Smallest Element in a Sorted Matrix
162. Find Peak Element
1529A - Eshag Loves Big Arrays
19. Remove Nth Node From End of List
925. Long Pressed Name
1051. Height Checker
695. Max Area of Island
402. Remove K Digits
97. Interleaving String
543. Diameter of Binary Tree
124. Binary Tree Maximum Path Sum
1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
501A - Contest
160A- Twins
752. Open the Lock
1535A - Fair Playoff
1538F - Interesting Function
1920. Build Array from Permutation
494. Target Sum
797. All Paths From Source to Target